GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Prime Restklassengruppe</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Prime Restklassengruppe</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die prime Restklassengruppe ist die <a href="Gruppe_(Mathematik)" title="Gruppe (Mathematik)">Gruppe</a> der <a href="Teilerfremdheit" title="Teilerfremdheit">primen</a> <a href="Restklasse" title="Restklasse">Restklassen</a> bezüglich eines Moduls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Sie wird als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bffe12a165220346c352fd4839b7c35dbaa08eb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}^{*}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f61825e3fdaaeb1c4839c3da1ec7bbecdcb4676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{n}^{*}}" loading="lazy"> notiert. Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im <a href="Restklassenring" title="Restklassenring">Restklassenring</a>. Die primen Restklassengruppen sind daher endliche <a href="Abelsche_Gruppe" title="Abelsche Gruppe">abelsche Gruppen</a> bezüglich der <a href="Multiplikation" title="Multiplikation">Multiplikation</a>. Sie spielen in der <a href="Kryptographie" title="Kryptographie">Kryptographie</a> eine bedeutende Rolle.

Die Gruppe besteht aus den Restklassen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy">, deren Elemente zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> <a href="Teilerfremd" class="mw-redirect" title="Teilerfremd">teilerfremd</a> sind. Gleichwertig dazu muss für den Repräsentanten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> der Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {ggT} (a,n)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {ggT} (a,n)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da94fb616de1f14fbf0fe6d742a1dd9e79aaf463.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.732ex; height:2.843ex;" alt="{\displaystyle \operatorname {ggT} (a,n)=1}" loading="lazy"> gelten, wobei ggT den <a href="Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler" title="Größter gemeinsamer Teiler">größten gemeinsamen Teiler</a> bezeichnet. Darauf weist die Bezeichnung „prime Restklasse“ hin, für teilerfremd sagt man auch relativ prim. Die <a href="Gruppenordnung" class="mw-redirect" title="Gruppenordnung">Gruppenordnung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}^{*}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f61825e3fdaaeb1c4839c3da1ec7bbecdcb4676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{n}^{*}}" loading="lazy"> ist durch den Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f067864064667dd5f8b2508b9cbf983d89788629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}" loading="lazy"> der <a href="Eulersche_%CF%86-Funktion" class="mw-redirect" title="Eulersche φ-Funktion">eulerschen φ-Funktion</a> gegeben.

<div class="mw-heading mw-heading2"><h2 id="Struktur">Struktur</h2></div>

Bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{p}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{p}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/537e72b1a70774ae976de89f7919dc0e0a9bb86d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.187ex; height:2.343ex;" alt="{\displaystyle v_{p}}" loading="lazy"> die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">-<a href="Bewertungstheorie" class="mw-redirect" title="Bewertungstheorie">Bewertung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> (die Vielfachheit des Primfaktors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">), ist also

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\prod _{p}p^{v_{p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e9e62d6b546cc85272d13819094f2dde2b407148.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:10.884ex; height:5.676ex;" alt="{\displaystyle n=\prod _{p}p^{v_{p}}}" loading="lazy"></dd></dl>

die <a href="Primfaktorzerlegung" title="Primfaktorzerlegung">Primfaktorzerlegung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, dann gilt:

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \prod _{p}(\mathbb {Z} /p^{v_{p}}\mathbb {Z} )^{\times }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b7f825a408f8bb99039a2b02fb24d4f1eac0418b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.664ex; height:5.676ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \prod _{p}(\mathbb {Z} /p^{v_{p}}\mathbb {Z} )^{\times }}" loading="lazy">

</mrow>

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</munder>

</mrow>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {}\cong {\begin{cases}\mathbb {Z} /2\mathbb {Z} \;\times \;\mathbb {Z} /2^{v_{2}-2}\mathbb {Z} \;\times \;\prod _{p\neq 2}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {falls} \ 8\mid n\\\prod _{p}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {sonst} .\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5e390d9108915aa57cf835700e73592f373d3d80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:62.553ex; height:7.509ex;" alt="{\displaystyle {}\cong {\begin{cases}\mathbb {Z} /2\mathbb {Z} \;\times \;\mathbb {Z} /2^{v_{2}-2}\mathbb {Z} \;\times \;\prod _{p\neq 2}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {falls} \ 8\mid n\\\prod _{p}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {sonst} .\end{cases}}}" loading="lazy"></dd>

<dd>oder mithilfe von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy"> und der Schreibweise <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"> für eine zyklische Gruppe ausgedrückt:</dd>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</munder>

<msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {}\cong {\begin{cases}C_{2}\;\times \;C_{2^{v_{2}-2}}\;\times \;\prod _{p\neq 2}C_{\varphi (p^{v_{p}})}&\mathrm {falls} \ 8\mid n\\\prod _{p}C_{\varphi (p^{v_{p}})}&\mathrm {sonst} .\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0864489e63898b96358b764231720ec9c494423.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:46.671ex; height:6.843ex;" alt="{\displaystyle {}\cong {\begin{cases}C_{2}\;\times \;C_{2^{v_{2}-2}}\;\times \;\prod _{p\neq 2}C_{\varphi (p^{v_{p}})}&\mathrm {falls} \ 8\mid n\\\prod _{p}C_{\varphi (p^{v_{p}})}&\mathrm {sonst} .\end{cases}}}" loading="lazy"></dd></dl></dd></dl>

Die erste Isomorphieaussage (Zerlegung des Moduls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> in seine Primfaktoren) folgt aus dem <a href="Chinesischer_Restsatz" title="Chinesischer Restsatz">chinesischen Restsatz</a>. Die zweite Isomorphieaussage (Struktur der primen Restklassengruppe modulo Primzahlpotenz) folgt aus der Existenz gewisser Primitivwurzeln<a href="#cite_note-Leutbecher-1">[1]</a> (siehe auch den zugehörigen Hauptartikel <a href="Primitivwurzel" title="Primitivwurzel">Primitivwurzel</a>).

Beachte: Mit den Gruppen ohne hochgestelltes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> sind die additiven Gruppen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} }">

</mrow>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67eff846b4a94fa19e547dc0b77fee953087b123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.38ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} }" loading="lazy"> etc. gemeint!

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bffe12a165220346c352fd4839b7c35dbaa08eb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}" loading="lazy"> ist genau dann <a href="Zyklische_Gruppe" title="Zyklische Gruppe">zyklisch</a>, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,4,p^{r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,2,4,p^{r}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e73373d88e24b510f1ff55f0d28243b698f8287.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.732ex; height:2.676ex;" alt="{\displaystyle 1,2,4,p^{r}}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2p^{r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2p^{r}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a5365b87e6ecba2c07b98bbfc15f47a3ac0e49d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.306ex; height:2.676ex;" alt="{\displaystyle 2p^{r}}" loading="lazy"> ist mit einer ungeraden <a href="Primzahl" title="Primzahl">Primzahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> und einer positiven Ganzzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">. Genau dann existieren auch <a href="Primitivwurzel" title="Primitivwurzel">Primitivwurzeln</a> modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, also Ganzzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, deren Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy"> ein <a href="Erzeuger_(Algebra)" class="mw-redirect" title="Erzeuger (Algebra)">Erzeuger</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bffe12a165220346c352fd4839b7c35dbaa08eb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}" loading="lazy"> ist.

<div class="mw-heading mw-heading2"><h2 id="Sonderfall:_Modul_ist_Primzahl">Sonderfall: Modul ist Primzahl</h2></div>

Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06d7948cc24bd2cce7c5a4322e5cbbea93c62c92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.663ex; height:2.009ex;" alt="{\displaystyle n=p}" loading="lazy"> eine Primzahl ist, wird für den (genau dann) ausgebildeten <a href="K%C3%B6rper" class="mw-disambig" title="Körper">Körper</a> (engl. Field) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /p\mathbb {Z} )}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /p\mathbb {Z} )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53e516dd9409bfafe7ac49d3d8650a75a7956509.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.242ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /p\mathbb {Z} )}" loading="lazy"> meist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{p}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{p}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d35035371db7bee93733c68c1802114c17d8bb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.479ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{p}}" loading="lazy"> geschrieben; es ist dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{p}^{\times }=\mathbb {F} _{p}\setminus \{{\bar {0}}\}}">

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{p}^{\times }=\mathbb {F} _{p}\setminus \{{\bar {0}}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82bc076e0e364238241d832a93fc818a809e99c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:14.191ex; height:3.343ex;" alt="{\displaystyle \mathbb {F} _{p}^{\times }=\mathbb {F} _{p}\setminus \{{\bar {0}}\}}" loading="lazy">; insbesondere ist die Gruppenordnung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \#\mathbb {F} _{p}^{\times }=\varphi (p)=p-1}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \#\mathbb {F} _{p}^{\times }=\varphi (p)=p-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4f68faa84c413e30a4e5dbb4535d5ced5403019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:20.735ex; height:3.176ex;" alt="{\displaystyle \#\mathbb {F} _{p}^{\times }=\varphi (p)=p-1}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Berechnung_der_inversen_Elemente">Berechnung der inversen Elemente</h2></div>

Zu jeder primen Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy"> existiert eine prime Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f36f90ec48b7a21a64dc9b6220fbc6f566eba8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.783ex; height:2.343ex;" alt="{\displaystyle b+n\mathbb {Z} }" loading="lazy">, sodass gilt:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/20396c04a7e4cf73d06934d7848620af9252de9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.567ex; height:2.843ex;" alt="{\displaystyle ab\equiv 1{\pmod {n}}}" loading="lazy"></dd></dl>

Die prime Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f36f90ec48b7a21a64dc9b6220fbc6f566eba8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.783ex; height:2.343ex;" alt="{\displaystyle b+n\mathbb {Z} }" loading="lazy"> ist also das inverse Element zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy"> bezüglich der Multiplikation in der primen Restklassengruppe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}^{*}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f61825e3fdaaeb1c4839c3da1ec7bbecdcb4676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{n}^{*}}" loading="lazy">. Ein Repräsentant von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f36f90ec48b7a21a64dc9b6220fbc6f566eba8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.783ex; height:2.343ex;" alt="{\displaystyle b+n\mathbb {Z} }" loading="lazy"> lässt sich mit Hilfe des <a href="Erweiterter_Euklidischer_Algorithmus" class="mw-redirect" title="Erweiterter Euklidischer Algorithmus">erweiterten euklidischen Algorithmus</a> bestimmen. Der Algorithmus wird auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> angewendet und liefert ganze Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, die folgende Gleichung erfüllen:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {ggT} (a,n)=1=s\cdot a+t\cdot n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/05da08fa3a8d762e51039937bf23a2a1e3f3c687.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.583ex; height:2.843ex;" alt="{\displaystyle \operatorname {ggT} (a,n)=1=s\cdot a+t\cdot n}" loading="lazy">.</dd></dl>

Daraus folgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\equiv sa{\pmod {n}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\equiv sa{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55a6ab9c8ae10c7422e7d54c1a1318b45ec4ae46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.66ex; height:2.843ex;" alt="{\displaystyle 1\equiv sa{\pmod {n}}}" loading="lazy">, das heißt, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> ist ein Repräsentant der zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy"> multiplikativ inversen Restklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f36f90ec48b7a21a64dc9b6220fbc6f566eba8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.783ex; height:2.343ex;" alt="{\displaystyle b+n\mathbb {Z} }" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

Die <a href="Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a> wurden von <a href="Carl_Friedrich_Gau%C3%9F" title="Carl Friedrich Gauß">Carl Friedrich Gauß</a> auf Latein veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

<ul><li><a href="Carl_Friedrich_Gau%C3%9F" title="Carl Friedrich Gauß">Carl Friedrich Gauß</a>: <a rel="nofollow" class="external text" href="https://gdz.sub.uni-goettingen.de/id/PPN373456743">Untersuchungen über höhere Arithmetik</a> (deutsche Übersetzung), Original: Leipzig 1801.</li></ul>

<ul><li>Armin Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-Leutbecher-1"><a href="#cite_ref-Leutbecher_1-0">↑</a> A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53–54.

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2022-08-07" href="https://de.wikipedia.org/wiki/?title=Prime_Restklassengruppe&oldid=225144478">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>